import java.util.HashSet;

public class No023 {
    /**
     * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
     */

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    // 辅助空间
    public ListNode EntryNodeOfLoop2(ListNode pHead){
        HashSet<ListNode> set = new HashSet<>();
        while (pHead != null){
            if (set.contains(pHead)) return pHead;
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }

    //node1先走一个环的长度，node2与node1相遇点就是环入口
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode meetingNode = MeetingNode(pHead);
        if (meetingNode == null) return null;
        int count = 1;
        ListNode node1 = meetingNode.next;
        while (node1 != meetingNode){
            node1 = node1.next;
            count++;
        }
        node1 = pHead;
        for (int i = 0; i < count; i++) {
            node1 = node1.next;
        }
        ListNode node2 = pHead;
        while (node1 != node2){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
    public ListNode MeetingNode(ListNode pHead){
        if (pHead ==null) return null;
        ListNode slow = pHead;
        ListNode fast = slow.next;
        while (fast !=null && slow!=null){
            if (fast == slow) return fast;
            slow = slow.next;
            fast = fast.next;
            if (fast!=null) fast = fast.next;
        }
        return null;
    }
}
